/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package mycollections;

import exceptions.MyIndexOutOfBoundsException;
import interfaces.MyList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.RandomAccess;
import mylist.MyLinkedList;
import mylist.MyListIterator;

/**
 *
 * @author Daryna_Ragimova
 */
public class MyCollections {
    
    /**
     * в случае RandomAccess выполнять быструю сортировку, иначе - сортировку пузырьком. 
     * Порядок элементов определяется результатом работы метода compareTo
     * @param list - list of the elements
     */
    public static void sort(MyList list){
        boolean isComparable = true;
        int size = list.size();
        for (int i = 0; i < size; i++) {
            Object o = list.get(i);
            if (!(o instanceof Comparable)) {
                isComparable = false;
                break;
            }
        }
        if (isComparable){
            if (list instanceof RandomAccess ){
                System.out.println("quickSort");
                quicksort(list,0,list.size()-1);
            }
            else{
                System.out.println("bubblesort");
                bubblesort(list);
            }
        }
        else{
            throw  new IllegalArgumentException("List's objects don't implement Comparable. "
                    + "Use the method sort(Mylist list, Comparator c)");
        }
    }  
    /**
     * если объект массива не реализует интерфейс Comparable, то должен передаваться объект реализующий интерфейс Comparator
     * @param list - list of elements
     * @param c - implementation for interface Comporator
     */
    public static <T> void sort(MyList<T> list, Comparator<? super T> c) {
        T[] a = (T[])list.toArray();
        Arrays.sort(a, (Comparator)c);
        
        if (list instanceof RandomAccess ){ 
            for (int j=0; j < a.length; j++) {
                list.set(j, a[j]);
            }
        }
        else{
            MyListIterator i =  list.iterator();
            for (int j = 0; j < a.length; j++){
               i.next();
               i.set(a[j]); 
               
            }
        }
    }
    /**
     * Swaps the elements at the specified positions in the specified list
     * @param list - list of elements
     * @param i - index of the first element for swap
     * @param j - index of the second element for swap
     */
    public static void swap(MyList<?> list, int i, int j) {
        MyList l =list;
        if (list instanceof RandomAccess ){ 
            Object a = l.get(j);
            l.set(j, l.get(i));
            l.set(i, a);
        }
        else{
            MyListIterator i1 = l.iterator(i);
            i1.next();
            Object x = i1.previous();
            MyListIterator i2 = l.iterator(j);
            i2.next();
            Object y = i2.previous();
            i1.set(y);
            i2.set(x);
        }
    } 
    /**
     * Copies all of the elements from one list into another
     * @param dest - the list to which we want to copy
     * @param src -the list from which we want to copy
     */
    public static <T> void copy(MyList<? super T> dest, MyList<? extends T> src) {
        int srcSize = src.size();
        if (srcSize > dest.size())
            throw new MyIndexOutOfBoundsException("Source does not fit in dest");

        if (src instanceof RandomAccess && dest instanceof RandomAccess) {
            for (int i=0; i<srcSize; i++)
                dest.set(i, src.get(i));
        } else {
            MyListIterator<? super T> di=(MyListIterator<? super T>) dest.iterator();
	    MyListIterator<? extends T> si=(MyListIterator<? extends T>) src.iterator();
            for (int i=0; i<srcSize; i++) {
                di.next();
                di.set(si.next());
                
            }
        }
    }
    /**
     * Reverses the order of the elements in the specified list
     * @param list - the list whose elements are to be reversed.
     */
    public static void reverse(MyList list){
         int size = list.size();
        if (list instanceof RandomAccess) {
            for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--)
                swap(list, i, j);
        } else {
            MyListIterator fwd = list.iterator();
            MyListIterator rev = list.iterator(size);
            for (int i=0, mid=list.size()>>1; i<mid; i++) {
                Object tmp = fwd.next();
                fwd.set(rev.previous());
                rev.set(tmp);
            }
        }
     }
    // реализует рекурсивный поиск в отсортированном массиве методом бисекции. 
    //Если элемент найден, то возвращается его индекс. Если не найден, то возвращается отрицательное значение, вычисляемое по следующей формуле:
    //(-(insertion point) - 1), где insertion point - индекс того места в массиве, где должен был бы быть указанный элемент.
    public static <T>
    int binarySearch(MyList<? extends Comparable<? super T>> list, T key) {
        if (list instanceof RandomAccess )
            return indexedBinarySearch(list, key);
        else
            return iteratorBinarySearch(list, key);
    }

    private static <T>
    int indexedBinarySearch(MyList<? extends Comparable<? super T>> list, T key)
    {
        int low = 0;
        int high = list.size()-1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            Comparable<? super T> midVal = list.get(mid);
            int cmp = midVal.compareTo(key);

            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found
    }

    private static <T>
    int iteratorBinarySearch(MyList<? extends Comparable<? super T>> list, T key)
    {
        int low = 0;
        int high = list.size()-1;
        MyListIterator<? extends Comparable<? super T>> i = (MyListIterator<? extends Comparable<? super T>>) list.iterator();

        while (low <= high) {
            int mid = (low + high) >>> 1;
            Comparable<? super T> midVal = get(i, mid);
            int cmp = midVal.compareTo(key);

            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found
    }
    private static <T> T get(MyListIterator<? extends T> i, int index) {
        T obj = null;
        int pos = i.nextIndex();
        if (pos <= index) {
            do {
                obj = i.next();
            } while (pos++ < index);
        } else {
            do {
                obj = i.previous();
            } while (--pos > index);
        }
        return obj;
    }

    private static void quicksort(MyList a, int left, int right) {
        if (right <= left) {
            return;
        }
        int i = partition(a, left, right);
        quicksort(a, left, i - 1);
        quicksort(a, i + 1, right);
    }

    private static int partition(MyList a, int left, int right) {
        int i = left - 1;
        int j = right;
        while (true) {
            Comparable q = (Comparable) a.get(++i);
            Comparable w = (Comparable) a.get(right);
            Comparable e = (Comparable) a.get(j);
            while (less(q, w)) {
                i++;
                q = (Comparable) a.get(i);
            }
            while (less(w, e)) {
                if (j == left) {
                    break;
                }
                e = (Comparable) a.get(j);
                j--;
            }
            if (i + 1 >= j) {
                break;
            }
            swap(a, i, j);
        }
        swap(a, i, right);
        return i;
    }

    private static void bubblesort(MyList a) {
        boolean flag = true;
        while (flag) {
            flag = false; 
            MyListIterator i = a.iterator();
            Comparable x = (Comparable)i.next();
            for (int j = 1; j <= a.size() - 1; j++) {
                Comparable y = (Comparable)i.next();
                if (less(x,y)) 
                {
                    i.previous();
                    i.previous();
                    i.set(y);
                    i.next();
                    i.next();
                    i.set(x);
                    flag = true;
                }
                else {
                    x = y;
                }
            }
        }
    }

    private static boolean less(Comparable x, Comparable y) {
        return (x.compareTo(y) > 0 ? true : false);
    }
    
}
